package com.github.yangyishe.p300;

/**
 * 221. 最大正方形
 * https://leetcode.cn/problems/maximal-square/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 * 输出：4
 * 示例 2：
 *
 *
 * 输入：matrix = [["0","1"],["1","0"]]
 * 输出：1
 * 示例 3：
 *
 * 输入：matrix = [["0"]]
 * 输出：0
 *
 *
 * 提示：
 *
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 300
 * matrix[i][j] 为 '0' 或 '1'
 */
public class Problem221 {
    public static void main(String[] args) {
        char[][] matrix=new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
//        char[][] matrix=new char[][]{{'0'}};

        Problem221 problem221 = new Problem221();
        int i = problem221.maximalSquare(matrix);
        System.out.println("i = " + i);
    }

    /**
     * 思路:
     * 暴力算法: 找到每一个1, 并逐次增大其预期边长, 直到最大边长的就是题解
     *
     * 构建一个与原矩阵相同的数字记录矩阵.
     * 矩阵的内容, dps[i][j]表示以matrix[i][j]为顶点之一, 可以构建的最大正方形.
     * 初始化, 最左侧和最上侧, 必定是matrix值本身.
     *
     * 如果matrix[i][j]='0', 则必然是0
     * 如果matrix[i][j]='1', 则为判定dps[i-1][j-1],dps[i-1][j],dps[i][j-1]是否相等. 如果相等, 则为三者相同值+1; 否则为三者最小值+1
     *
     *
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        //1. 创建dps
        int[][] dps=new int[matrix.length][matrix[0].length];

        //2. 初始化
        int maxSqu=0;
        for(int i=0;i<matrix.length;i++){
            dps[i][0]=matrix[i][0]-'0';
            maxSqu=Math.max(dps[i][0],maxSqu);
        }
        for(int i=0;i<matrix[0].length;i++){
            dps[0][i]=matrix[0][i]-'0';
            maxSqu=Math.max(dps[0][i],maxSqu);
        }

        //3. 遍历推进
        for(int r=1;r<matrix.length;r++){
            for(int c=1;c<matrix[0].length;c++){
                if(matrix[r][c]=='1'){
                    int minSqu=Math.min(dps[r-1][c-1],dps[r-1][c]);
                    minSqu=Integer.min(minSqu,dps[r][c-1]);
                    dps[r][c]=minSqu+1;

                    maxSqu=Math.max(dps[r][c],maxSqu);
                }else{
                    dps[r][c]=0;
                }

            }
        }

        //4. 返回
        return maxSqu*maxSqu;
    }
}
